#include <stdint.h>
#include <string.h>
#include <malloc.h>

#include "sudoku.h"

#define SHOW_PREPRODESS_STATUS

// 求k,使得2的k次方等于m
// m必须是2的k次方的形式, k>=1 且 k<=9
int log2(BitsType m)
{
    for (int i=9;i>=1;i--)
    {
        if ( (m & (1<<i))>0)
            return i;
    }
    return 0;
}

// a是输入数组,包含9*9=81个整数
// a[row*9+col]>0, 表示第row行第col列填充的数字,
// a[row*9+col]==0,表示第row行col列的数字是未知的，需要计算出来
void Sudoku::init( int a[])
{
    BitsType rowCandidate[9];   // 每行中的空白格子的候选数字掩码
    BitsType colCandidate[9];   // 每列中的空白格子的候选数字掩码．
    BitsType blkCandidate[9];   // 每个宫中的空白格子的候选数字掩码．
    //以下代码将３个数组初始化为FULLBITS，表示对应的行，列，宫中的空位可填充的数字可以是１,2,3,4,5,6,7,8,9
    for (int i=0;i<9;i++)
        rowCandidate[i]=colCandidate[i]=blkCandidate[i]=FULLBITS;

    // 第一轮(round=0)，用于计算 rowCandidate，colCandidate和blkCandidate
    // 第二轮(round=1)，用于计算空白格子可能的取值 cells[row][col].candidate
    for (int round=0;round<2;round++)
    {
        for (int i=0;i<9*9;i++)
        {
            int row=i/9;  // 行号
            int col=i%9;  // 列号
            int d=a[i];
            int blkNo= BLOCK_NO(row,col); // 宫的序号
            if (  d<0 || d>9 )
            {
                printf("Invalid input");
                exit(1);
            }
            if ( round==0 && d>=1 && d<=9)
            {
                cells[row][col].flag=KNOWN;
                cells[row][col].num=d;
                CLEAR_BIT(rowCandidate[row],d); //rowCandidate[row]的第d位清0. 表示对应的行中的任意空白格子不可以是d
                CLEAR_BIT(colCandidate[col],d);  //rowCandidate[col]的第d位清0. 表示对应的行中的任意空白格子不可以是
                CLEAR_BIT(blkCandidate[blkNo],d); //blkCandidate[blkNo]的第d位清0.　表示对应的宫中的任意空白格子不可以是d
            }
            else if ( round==1 && d==0)
            {
                cells[row][col].flag=UNKNOWN;
                cells[row][col].num=0;
                // cells[row][col].candidate 为row行col列的格子可能的取值 
                cells[row][col].candidate=(rowCandidate[row] & colCandidate[col] & blkCandidate[blkNo]);
            }
        }
    }
}

//更新相关格子的candidate字段，将第row行的所有空位的候选数字标记为不可为n
int Sudoku::eliminateCandidateInRow(int row,int d)
{
    int c=0;//有多少个格子的candidate被改变
    for (int i=0;i<9;i++)
    {
        if ( cells[row][i].flag==UNKNOWN )
        {
            BitsType old = cells[row][i].candidate;
            CLEAR_BIT(cells[row][i].candidate,d);
            c += (cells[row][i].candidate != old);
        }
    }
    return c; //返回更新次数
}

//更新相关格子的candidate字段，将第col列的所有空位的候选数字标记为不可为n
int Sudoku::eliminateCandidateInCol(int col,int d)
{
    int c=0;//有多少个格子的candidate被改变
    for (int i=0;i<9;i++)
    {
        if (cells[i][col].flag==UNKNOWN )
        {
            BitsType old=cells[i][col].candidate;
            CLEAR_BIT(cells[i][col].candidate,d);
            c += (cells[i][col].candidate != old);
        }
    }
    return c; //返回更新次数
}

//更新相关格子的candidate字段，将第blkNo宫中的所有空位的候选数字标记为不可为n
int Sudoku::eliminateCandidateInBlock(int blkNo,int d)
{
    int c=0;            //有多少个格子的candidate被改变
    int R=(blkNo/3)*3;  // 宫blockNo左上角的行号
    int C=(blkNo%3)*3;  // 宫blockNo左上角的列号　
    std::pair<int,int> offsets[9]={ {0,0},{0,1},{0,2}, {1,0},{1,1},{1,2},{2,0},{2,1},{2,2}};
    for (int i=0;i<9;i++)
    {
        int y=offsets[i].first; 
        int x=offsets[i].second;
        // cells[R+y][C+x]中的数字是尚未确定
        if (cells[R+y][C+x].flag==UNKNOWN )
        {
            BitsType old=cells[R+y][C+x].candidate;
            CLEAR_BIT(cells[R+y][C+x].candidate,d);
            c += (cells[R+y][C+x].candidate != old);
        }
    }
    return c; //返回更新次数
}

// 预处理，处理一些简单的情况，计算出只有一个可选项的空白格子的可填充的数字
void  Sudoku::preprocess()
{
    while (true)
    {
        int c=0; //将c初始化为0
        for (int i=0;i<9*9;i++)
        {
            int row=i/9; //row:行号，从0开始
            int col=i%9; //col:列号，从0开始
            if ( cells[row][col].flag==UNKNOWN && IS_POWER2(cells[row][col].candidate))
            {
                int d = log2(cells[row][col].candidate);
                int blkNo= BLOCK_NO(row,col); // 宫的序号
                cells[row][col].num = d;  //空白格子的数字被确定
                cells[row][col].flag=KNOWN;
                c += eliminateCandidateInRow(row,d);    //从row行的所有空位的候选数字中删除d
                c += eliminateCandidateInCol(col,d);    //从col列的所有空位的候选数字中删除d
                c += eliminateCandidateInBlock(blkNo,d); //从block宫中的所有空位的候选数中删除d
            }
        }
        if (c==0 ) // 如果没有新的空白格子的数字被确定，则结束处理
            break;
    }
}

void Sudoku::createAdvancedSearchContext()
{
    BlankCell cell;
    memset(&cell,0,sizeof(cell));
    blankCells.push_back(cell); // blankCells[0]不使用
    for (int row=0;row<9;row++)
    {
        for (int col=0;col<9;col++)
        {
            if ( cells[row][col].flag==UNKNOWN )
            {
                cell.row=row;
                cell.col=col;
                cell.block=BLOCK_NO(row,col); // 宫的序号;
                cell.cs.init(cells[row][col].candidate);
                blankCells.push_back(cell);
            }
        }
    }

    reltvTable.clear(); // relatives table 亲属表,清空
    uint8_t lastCellID=blankCells.size()-1;
    for ( int i=1;i<lastCellID;i++)
    {
        size_t count=0;
        blankCells[i].reltvAddr=(uint16_t)reltvTable.size();
        for (int j=i+1;j<=lastCellID;j++)
        {
            if (   blankCells[j].row== blankCells[i].row
                || blankCells[j].col== blankCells[i].col
                || blankCells[j].block== blankCells[i].block)
            {
                reltvTable.push_back(j); 
                count++;
            }
        }
        blankCells[i].reltvCount=(uint8_t)count;
    }
}

//尝试填充ID大于等于currLayID空白格子，这是一个递归函数
void Sudoku::tryFill(uint8_t currLayID,outputCallBack fun,void *pContent) 
{
    BlankCell *pCurrCell= &(blankCells[currLayID]);
    uint8_t lastID=(uint8_t)(blankCells.size()-1);
    BitsType candidate;

    if (currLayID==lastID )
    {
        candidate= blankCells[currLayID].cs.get(currLayID);
        uint8_t d=log2(candidate);
        cells[pCurrCell->row][pCurrCell->col].num=d;
        fun(pContent,cells);
        return ;
    }

    for (int d=1;d<=9;d++)
    {
        candidate= blankCells[currLayID].cs.get(currLayID);
        if ( candidate & (1<<d) )
        {
            //printf("Debug:currLayID=%d,d=%d,candidate=",currLayID,d);
            //print_mask(candidate,0,true); printf("\n");

            cells[pCurrCell->row][pCurrCell->col].num=d;
            //printf("Debug:fill cell[%d][%d] with %d\n",blankCells[currLayID].row,blankCells[currLayID].col,d);

            //尝试更新ID大于currLayID 的 statusSerial
            bool bRet=true;
            for (uint8_t i=0;i<pCurrCell->reltvCount;i++)
            {
                uint8_t tid=reltvTable[pCurrCell->reltvAddr+i];
                if (! blankCells[tid].cs.update(currLayID,d) )
                {
                    //printf("Debug:tid=%d,Update cell[%d][%d] failed\n",tid,blankCells[tid].row,blankCells[tid].col);
                    bRet=false;
                    break;
                }
            }

            if ( bRet)
                tryFill(currLayID+1,fun,pContent);  //递归调用，填充下一个空白格子
        }
    }
}

void Sudoku::resolve(outputCallBack fun,void *pContent)
{
    preprocess();
    createAdvancedSearchContext();
    if ( blankCells.size()==1)
    {
        fun(pContent,cells);
        return;
    }
#ifdef  SHOW_PREPRODESS_STATUS
    printf("---The sudoku status---\n");
    printStatus(NULL, cells);
#endif

    tryFill(1,fun,pContent);
}
